package tree;

/**
 * @author : Rookie
 * @description : 二叉搜索树修剪
 * @date : 2023/11/2
 */
public class BinarySearchTreePrune {

    public static void main(String[] args) {
        int[] tree = new int[] {3,2,7,1,-1,5,9,-1,-1,-1,-1,4,6,8,10};
        TreeNode root = BinaryTreeUtil.buildTree(tree);
        System.out.println("========修剪之前========");
        BinaryTreeUtil.Traversal.sequenceTraversal(root);
        int start = 4,end=8;
        TreeNode treeNode = prune(root, start, end);
        System.out.println("\n========修剪之后========");
        BinaryTreeUtil.Traversal.sequenceTraversal(treeNode);
    }

    private static TreeNode prune(TreeNode root,int start,int end) {
        if (root == null) {
            return null;
        }
        // 处理根节点
        if (root.element < start) {
            // 根节点比下限小，那么根节点的左子树一定比下限小，只用遍历右子树
           return prune(root.right,start,end);
        }
        if (root.element > end) {
            // 根节点比下限大，那么根节点的右子树一定比下限大，只用遍历左子树
            return prune(root.left,start,end);
        }

        root.left = prune(root.left,start,end);
        root.right = prune(root.right,start,end);
        return root;
    }
}
